//
//  912. 排序数组(手撕堆排序).swift
//  Top600
//
//  Created by rjb on 2021/8/5.
//

import Foundation
class Solution912_2 {
    // 堆排序，从小到大排序，采用小顶堆
    // 仅仅只是排序的话只需要上滤可以了
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        // 构建大顶堆
        for i in (0..<nums.count/2).reversed() {
            heapify(&nums, length: nums.count, index: i)
        }
        // 在已经建立有堆的基础上，将堆顶元素取出，放到最后，在重新调整堆
        for i in (0..<nums.count).reversed() {
            // 堆顶元素与最后元素替换
            let tmp = nums[0]
            nums[0] = nums[i]
            nums[i] = tmp
            
            // 重新调整堆
            heapify(&nums, length: i, index: 0)
        }
        return nums
    }
    // 在指定的堆大小length里，调整index的位置
    // 将index的元素不断的写沉
    func heapify(_ nums: inout [Int], length: Int, index: Int) {
        let v = nums[index]
        var index = index
        // 根节点从0开始
        while index < length / 2 {
            var childIndex = index * 2 + 1
            let rightIndex = childIndex + 1
            // 如果右子节点存在，且比左要打，上移的是右
            if rightIndex < length && nums[rightIndex] > nums[childIndex] {
                childIndex = rightIndex
            }
            // 如果最大的比当前的还小。则不用移动了
            if nums[childIndex] < v {
                break
            }
            nums[index] = nums[childIndex]
            index = childIndex
        }
        nums[index] = v
    }
   
    static func test() {
        let solution = Solution912_2()
        let nums = [4, 5, 8, 2, 3, 9, 7, 1]
        let result = solution.sortArray(nums)
        print(result)
    }
}
